package 算法.查找;

import java.util.HashMap;

import util.CompareUtils;
import util.LogUtils;
import com.sun.org.apache.regexp.internal.recompile;

/**
 * 【红黑树】
 * 	左右旋转：保证 不会出现右红和连续红
 * 			和AVL的旋转好像不太一样
 * 	注：红黑树像继承了BST一样，BST中的查询方法均可使用
 * @Date   2017-09-02
 * @author Administrator
 * @version TODO:>>>>>>>尚未测试
 */
public class RedBlackBST <K extends Comparable<K>, V> {
	private Node root;										//本红黑树根节点
	private static final boolean RED = true, BLACK = false;
	private class Node {
		K k;
		V v;
		boolean color;
		Node left, right;
		int N;

		public Node(K k, V v, boolean color, int n) {
			super();
			this.k = k;
			this.v = v;
			this.color = color;
			N = n;
		}

		@Override
		public String toString() {
			return "Node [k=" + k + ", v=" + v + ", color=" + color + ", N="
					+ N + "]";
		}
	}
	
	private Integer size(Node node) {
		if (node == null)	return 0;
		return size(node.left) + size(node.right) + 1;
	}
	
	/**
	 * 判断某个节点是否为红节点
	 * @param node
	 * @return
	 */
	private boolean isRed(Node node) {
		if (node == null) 	return BLACK;		//红黑树根节点为Black
		return node.color == RED;
	}
	
	/**
	 * 左旋：出现右红节点时左旋
	 * @param h 该(子)树的原根节点h
	 * @return	返回旋转后该(子)树的根节点x
	 */
	public Node rotateLeft(Node h) {
		Node x = h.right;
		h.right = x.left;
		x.left = h;
		x.color = h.color;
		h.color = RED;
		x.N = h.N;				//TODO:为什么
		h.N = size(h); 
		return x;
	}
	
	
	/**
	 * 右旋：当连续两个左红节点时右旋
	 * @param h
	 * @return
	 */
	public Node rotateRight(Node h) {
		Node x = h.left;
		h.left = x.right;
		x.right = h;
		x.color = h.color;
		h.color = RED;
		x.N = h.N;
		h.N = size(h);
		return x;
	}
	
	/**
	 * 颜色转换：当左右都为红节点时(临时4节点)，颜色转换
	 * @param h
	 */
	public void flipColor(Node h) {
		h.left.color = BLACK;
		h.right.color = BLACK;
		h.color = RED;
	}

	/**
	 * put方法：
	 * @param k
	 * @param v
	 */
	public void put(K k, V v) {
		root = put(root, k, v);
		root.color = BLACK;				//红黑树根节点为Black
	}
	
	
	private Node put(Node root, K k, V v) {
		if (root == null)	return new Node(k, v, RED, 1);		//默认按照单个2-变3-新插入的节点为红色
		//与BST的put完全一致
		int rsCompare = CompareUtils.compareTo(root.k, k);
		if (rsCompare > 0) 		root.left  = put(root.left,  k, v);
		else if (rsCompare < 0)	root.right = put(root.right, k, v);
		else 					root.v = v;
		//通过颜色，平衡调整
		if (isRed(root.right))							root = rotateLeft(root);
		if (isRed(root.left) && isRed(root.left.left))	root = rotateRight(root);
		if (isRed(root.left) && isRed(root.right))		flipColor(root);
		root.N = size(root);
		return root;
	}
	
	public void traverse() {
		traverse(root);
	}

	/**
	 * 中序遍历
	 */
	public void traverse(Node root) {
		if (root == null) return;
		traverse(root.left);
		LogUtils.println("Red-Black BST 中序遍历", root);
		traverse(root.right);
	}

	public static void main(String[] args) {
		RedBlackBST<String, Integer> rbBst = new RedBlackBST<String, Integer>();
		rbBst.put("D", 4);
		rbBst.put("E", 5);
		rbBst.put("B", 2);
		rbBst.put("C", 3);
		rbBst.put("A", 1);
		rbBst.traverse();
	}
}
